Hereditary structural completeness is established for a range of substructural logics, mainly without the weakening rule, including fragments of various relevant or many-valued logics. Also, structural completeness is disproved for a range of systems, settling some previously open questions.

A full separation theorem for the derivable rules of intuitionistic linear logic without bounds, 0 and exponentials is proved. Several structural consequences of this theorem for subreducts of (commutative) residuated lattices are obtained. The theorem is then extended to the logic LR+ and its proof is extended to obtain the finite embeddability property for the class of square increasing residuated lattices.

We study the computational complexity of the universal and quasi-equational theories of classes of bounded distributive lattices with a negation operation, i.e., a unary operation satisfying a subset of the properties of the Boolean negation. The upper bounds are obtained through the use of partial algebras. The lower bounds are either inherited from the equational theory of bounded distributive lattices or obtained through a reduction of a global satisfiability problem for a suitable system of propositional modal logic.

A biresiduation algebra is a 〈/,\,1〉-subreduct of an integral residuated lattice. These algebras arise as algebraic models of the implicational fragment of the Full Lambek Calculus with weakening. We axiomatize the quasi-variety B of biresiduation algebras using a construction for integral residuated lattices. We define a filter of a biresiduation algebra and show that the lattice of filters is isomorphic to the lattice of B-congruences and that these lattices are distributive. We give a finite basis of terms for generating filters (...) and use this to characterize the subvarieties of B with EDPC and also the discriminator varieties. A variety generated by a finite biresiduation algebra is shown to be a subvariety of B. The lattice of subvarieties of B is investigated; we show that there are precisely three finitely generated covers of the atom. (shrink)

The logics considered here are the propositional Linear Logic and propositional Intuitionistic Linear Logic extended by a knotted structural rule: γ, xn → y / γ, xm → y. It is proved that the class of algebraic models for such a logic has the finite embeddability property, meaning that every finite partial subalgebra of an algebra in the class can be embedded into a finite full algebra in the class. It follows that each such logic has the finite model property (...) with respect to its algebraic semantics and hence that the logic is decidable. (shrink)

We study the computational complexity of the universal theory of residuated ordered groupoids, which are algebraic structures corresponding to Nonassociative Lambek Calculus. We prove that the universal theory is co $$\textsf {NP}$$ -complete which, as we observe, is the lowest possible complexity for a universal theory of a non-trivial class of structures. The universal theories of the classes of unital and integral residuated ordered groupoids are also shown to be co $$\textsf {NP}$$ -complete. We also prove the co $$\textsf {NP}$$ (...) -completeness of the universal theory of classes of residuated algebras, algebraic structures corresponding to Generalized Lambek Calculus. (shrink)